/**
 * @file 116.PopulatingNextRightPointer.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-13
 * 
 * @copyright Copyright (c) 2021
 * 
 * 节点特殊，另开一个文件，层序十一连
 * 116.填充指向下一个右侧节点的指针
 * 117.填充指向下一个右侧节点的指针II
 */

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

class Node
{
public:
    int val;
    Node *left;
    Node *right;
    Node *next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node *_left, Node *_right, Node *_next)
        : val(_val), left(_left), right(_right), next(_next) {}
};

class Solution
{
public:
    // 116.
    Node *connect(Node *root)
    {
        // 递归解
        if (root == nullptr) {
            return root;
        }
        connect(root->left, root->right);
        return root;
    }
    void connect(Node *node1, Node *node2)
    {
        if (node1 == nullptr) {
            return;
        }
        node1->next = node2;
        connect(node1->left, node1->right);
        connect(node1->right, node2->left);
        connect(node2->left, node2->right);
    }
    // 116.+117. 层序 完全复用
    // 117.的递归有亿点点复杂
    Node *connect2(Node *root)
    {
        queue<Node *> q;
        if (root) {
            q.push(root);
        }
        while (!q.empty()) {
            int n = q.size();
            while (n--) {
                Node *node = q.front();
                q.pop();
                if (n) { // 如果当前节点不是该层最后一个节点
                    node->next = q.front();
                }
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
        }
        return root;
    }
};